//6.55 为二叉链表的结点增加DescNum域。试编写一算法，求二叉树的每个结点的子孙数目并存入其DescNum域。请给出算法的时间复杂度。
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"
// data == DescNum
// On(n)
int fun_6_55_1(tree *&root)
{
    if (root)
    {
        if (root->left && root->left)
        {
            root->data = fun_6_55_1(root->left) + fun_6_55_1(root->right) + 2;
        }
        else if (!root->left && !root->right)
        {
            root->data = 0;
        }
        else
        {
            if (root->left)
            {
                root->data = fun_6_55_1(root->left) + 1;
            }
            if (root->right)
            {
                root->data = fun_6_55_1(root->right) + 1;
            }
        }
        return root->data;
    }
    else
        return -1;
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  1, 1,
                  1, 1, 1, NULL,
                  1, 1, NULL, 1, NULL, 1, NULL, NULL};
    tree *root;
    CreatTree(root, a1, n, 0);
    fun_6_55_1(root);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
